/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //验证回文串 II
    public boolean validPalindrome(String s) {
        char[] chars = s.toCharArray();
        return isHui(chars, 0, chars.length-1, true);
    }

    private boolean isHui(char[] chars, int l, int r, boolean hasChance) {
        if (l >= r) {
            return true;
        }
        // 如果相等，继续向中间靠拢
        if (chars[l] == chars[r]) {
            return isHui(chars, l+1, r-1, hasChance);
        }
        // 如果不相等，且没有机会，返回失败
        if (!hasChance) {
            return false;
        }
        // 删除左边或删除右边
        return isHui(chars, l+1, r, false) || isHui(chars, l, r-1, false);
    }

    //构成特定和需要添加的最少元素
    public int minElements(int[] nums, int limit, int goal) {
        long sum = 0;
        for (int a : nums) {
            sum += a;
        }
        long diff = goal - sum;
        return (int) (Math.abs(diff / limit) + (diff % limit == 0 ? 0 : 1));
    }
}
